#include <vector>
#include <cstring>
using namespace std;
/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */

// @lc code=start
class Solution {
public:
    bool rows[9][9], columns[9][9], boxes[3][3][9];
    bool flag = false;
    void solveSudoku(vector<vector<char>>& board) {
        memset(rows, 0, sizeof rows);
        memset(columns, 0, sizeof rows);
        memset(boxes, 0, sizeof boxes);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int index = board[i][j] - '1';
                rows[i][index] = columns[j][index] = boxes[i / 3][j / 3][index] = true;
            }
        }
        dfs(0, 0, board); 
    }

    // 1, 2
    // 11 
    void dfs(int r, int c, vector<vector<char>>& board) {
        if (flag) return;
        if (r == 9 && c == 0) {
            flag = true;
            return;
        }
        int num = r * 9 + c + 1;
        if (!flag && board[r][c] != '.') {
            dfs(num / 9, num % 9, board);
            if (flag) return;
        } else {
            for (char i = '1'; i <= '9' && !flag; i++) {
                int index = i - '1';
                if (!flag && !rows[r][index] && !columns[c][index] && !boxes[r / 3][c / 3][index]) {
                    rows[r][index] = columns[c][index] = boxes[r / 3][c / 3][index] = true;
                    board[r][c] = i;
                    dfs(num / 9, num % 9, board);
                    if (flag) return;
                    rows[r][index] = columns[c][index] = boxes[r / 3][c / 3][index] = false;
                    board[r][c] = '.';
                }
            }
        }
    }
};
// @lc code=end

